package cn.demoncat.util.lang.entity.data;

import java.util.function.Consumer;

/**
 * 顺序存储二叉树
 * 
 * 存储：数组
 * 功能：以二叉树（完全二叉树）的逻辑来操作底层数组
 * 
 * @author 延晓磊
 *
 * @since 2020年7月18日
 */
public class ArrayBinaryTree<T> {

	// 底层存储数组
	private T[] arr;
	
	/**
	 * 构建
	 * 
	 * @param arr	数据
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public ArrayBinaryTree(T[] arr) {
		super();
		this.arr = arr;
	}
	
	/**
	 * 底层数据
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月22日
	 */
	public T[] getArr() {
		return arr;
	}

	public void setArr(T[] arr) {
		this.arr = arr;
	}

	/**
	 * 前序遍历：结点 > 左子树 > 右子树
	 * 
	 * @param fn	消费者
	 * 
	 * @return 是否遍历（数据为空返回false）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public boolean preOrder(Consumer<T> fn) {
		if (arr == null || arr.length == 0) {
			return false;
		}
		// 从根结点开始遍历
		preOrder(0, fn);
		return true;
	}
	
	/**
	 * 中序遍历：左子树 > 结点 > 右子树
	 * 
	 * @param fn	消费者
	 * 
	 * @return 是否遍历（数据为空返回false）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public boolean inOrder(Consumer<T> fn) {
		if (arr == null || arr.length == 0) {
			return false;
		}
		// 从根结点开始遍历
		inOrder(0, fn);
		return true;
	}
	
	/**
	 * 后序遍历：左子树 > 右子树 > 结点
	 * 
	 * @param fn	消费者
	 * 
	 * @return 是否遍历（数据为空返回false）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	public boolean postOrder(Consumer<T> fn) {
		if (arr == null || arr.length == 0) {
			return false;
		}
		// 从根结点开始遍历
		postOrder(0, fn);
		return true;
	}
	
	/**
	 * 打印 - 中序遍历
	 * 
	 * @return
	 *
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	@Override
	public String toString() {
		StringBuilder sd = new StringBuilder("[");
		if (inOrder(data -> sd.append(data).append(", "))) {
			sd.delete(sd.length()-2, sd.length());
		}
		sd.append("]");
		return sd.toString();
	}
	
	
	/**
	 * 前序遍历：结点 > 左子树 > 右子树
	 * 
	 * @param i		结点索引，0表示根结点
	 * @param fn	消费者
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	private void preOrder(int i, Consumer<T> fn) {
		// 操作结点
		fn.accept(arr[i]);
		// 遍历左子树
		i = 2 * i + 1;
		if (i < arr.length) {
			preOrder(i, fn);
			// 遍历右子树
			i = i + 1;
			if (i < arr.length) {
				preOrder(i, fn);
			}
		}
	}
	
	/**
	 * 中序遍历：左子树 > 结点 > 右子树
	 * 
	 * @param i		结点索引，0表示根结点
	 * @param fn	消费者
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	private void inOrder(int i, Consumer<T> fn) {
		// 遍历左子树
		if (2 * i + 1 < arr.length) {
			inOrder(2 * i + 1, fn);
		}
		// 操作结点
		fn.accept(arr[i]);
		// 遍历右子树
		if (2 * i + 2 < arr.length) {
			inOrder(2 * i + 2, fn);
		}
	}
	
	/**
	 * 后序遍历：左子树 > 右子树 > 结点
	 * 
	 * @param i		结点索引，0表示根结点
	 * @param fn	消费者
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月18日
	 */
	private void postOrder(int i, Consumer<T> fn) {
		// 遍历左子树
		if (2 * i + 1 < arr.length) {
			postOrder(2 * i + 1, fn);
		}
		// 遍历右子树
		if (2 * i + 2 < arr.length) {
			postOrder(2 * i + 2, fn);
		}
		// 操作结点
		fn.accept(arr[i]);
	}
	
	
}
